{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Draw Line LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: drawLine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #绘制直线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>已知一个由像素点组成的单色屏幕，每行均有 <code>w</code> 个像素点，所有像素点初始为 <code>0</code>，左上角位置为 <code>(0,0)</code>。</p>\n",
    "\n",
    "<p>现将每行的像素点按照「每 <code>32</code> 个像素点」为一组存放在一个 <code>int</code> 中，再依次存入长度为 <code>length</code> 的一维数组中。</p>\n",
    "\n",
    "<p>我们将在屏幕上绘制一条从点 <code>(x1,y)</code> 到点 <code>(x2,y)</code> 的直线（即像素点修改为 <code>1</code>），请返回绘制过后的数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>用例保证屏幕宽度 <code>w</code> 可被 32 整除（即一个 <code>int</code> 不会分布在两行上）</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：length = 1, w = 32, x1 = 30, x2 = 31, y = 0\n",
    "<strong> 输出</strong>：[3]\n",
    "<strong> 解释</strong>：在第 0 行的第 30 位到第 31 位画一条直线，屏幕二进制形式表示为 [00000000000000000000000000000011]，因此返回 [3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：length = 3, w = 96, x1 = 0, x2 = 95, y = 0\n",
    "<strong> 输出</strong>：[-1, -1, -1]\n",
    "<strong> 解释</strong>：由于二进制 <strong>11111111111111111111111111111111</strong> 的 int 类型代表 -1，因此返回 [-1,-1,-1]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= w &lt;= 3 * 10^5</code></li>\n",
    "\t<li><code>0 &lt;= x1 &lt;= x2 &lt; w</code></li>\n",
    "\t<li><code>0 &lt;= y &lt;= 10</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [draw-line-lcci](https://leetcode.cn/problems/draw-line-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [draw-line-lcci](https://leetcode.cn/problems/draw-line-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        n = w // 32\n",
    "        res = [0] * length\n",
    "        start_p = y * n\n",
    "        for i in range(n):\n",
    "            s = i * 32\n",
    "            e = s + 31\n",
    "            if x1 > e:\n",
    "                res[i + start_p] = 0\n",
    "            elif x2 < s:\n",
    "                res[i + start_p] = 0\n",
    "            elif x2 > e and x1 <= s:\n",
    "                res[i + start_p] = -1\n",
    "            elif x2 > e and x1 > s:\n",
    "                digits = 32 - (x1 - s)\n",
    "                res[i + start_p] = (1 << digits) - 1\n",
    "            elif x2 <= e and x1 <= s:\n",
    "                digits = e - x2\n",
    "                res[i + start_p] = ~ ((1 << digits) - 1)\n",
    "            elif x2 <= e and x1 > s:\n",
    "                left = 32 - (x1 - s)\n",
    "                right = e - x2\n",
    "                res[i + start_p] = ((1 << left) - 1) & ( ~ ((1 << right) - 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        nums = [0] * length\n",
    "        m = w // 32\n",
    "        for i in range(length):\n",
    "            row, col = i // m, i % m\n",
    "            if row != y:\n",
    "                continue\n",
    "            x_left = col * 32\n",
    "            x_right = x_left + 31\n",
    "            if x_right < x1 or x_left > x2:\n",
    "                continue\n",
    "            if x_left >= x1 and x_right <= x2:\n",
    "                nums[i] = -1\n",
    "            else:\n",
    "                temp = 1\n",
    "                for j in range(x_right, x_left, -1):\n",
    "                    if j >= x1 and j <= x2:\n",
    "                        nums[i] += temp\n",
    "                    temp *= 2\n",
    "                if x_left >= x1 and x_left <= x2:\n",
    "                    nums[i] -= 2**31\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [0]*length\n",
    "        i, j = x1//32, x2//32\n",
    "        cnt = w//32\n",
    "        sta = (1<<(32-x1%32))-1\n",
    "        end = ((1<<(x2%32+1))-1)<<(31-x2%32)\n",
    "        flag = -1 if (end>>31)&1 else 1\n",
    "        flag1 = -1 if (sta>>31)&1 else 1\n",
    "        end = -(end^(0xffffffff))-1 if flag==-1 else end\n",
    "        sta = -(sta^(0xffffffff))-1 if flag1==-1 else sta\n",
    "        if i==j:res[y*cnt+x1//32]=sta&end\n",
    "        else:\n",
    "            res[y*cnt+x1//32:y*cnt+x2//32+1] = [sta]+[-1]*(j-i-1)+[end]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [0] * length\n",
    "        wid = w // 32\n",
    "        n1, m1 = divmod(x1, 32)\n",
    "        n2, m2 = divmod(x2, 32)\n",
    "        \n",
    "        for i in range(wid * y + n1, wid * y + n2 + 1):\n",
    "            res[i] = -1\n",
    "\n",
    "        if m1: res[wid * y + n1] &= (1 << (32 - m1)) - 1\n",
    "        res[wid * y + n2] ^= (1 << (31 -m2)) - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [0]*length\n",
    "        start = y*(w//32)\n",
    "        s = '0'*x1 + '1'*(x2-x1+1) + '0'*(w-x2-1)\n",
    "        for i in range(0, w, 32):\n",
    "            num = int(s[i:i+32], 2)\n",
    "            if s[i] == '1':\n",
    "                num = (num - 1) ^ 0xffffffff\n",
    "                num *= -1\n",
    "            res[start] = num\n",
    "            start += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [0]*length\n",
    "        i, j = x1//32, x2//32\n",
    "        cnt = w//32\n",
    "        sta = (1<<(32-x1%32))-1\n",
    "        end = ((1<<(x2%32+1))-1)<<(31-x2%32)\n",
    "        flag = -1 if (end>>31)&1 else 1\n",
    "        flag1 = -1 if (sta>>31)&1 else 1\n",
    "        end = -(end^(0xffffffff))-1 if flag==-1 else end\n",
    "        sta = -(sta^(0xffffffff))-1 if flag1==-1 else sta\n",
    "        if i==j:res[y*cnt+x1//32]=sta&end\n",
    "        else:\n",
    "            # print(y*cnt+x1//32,(y+1)*cnt,i,j,cnt)\n",
    "            res[y*cnt+x1//32:y*cnt+x2//32+1] = [sta]+[-1]*(j-i-1)+[end]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        r = [0] * length\n",
    "        sti = y * w // 32\n",
    "        st = sti + x1 // 32\n",
    "        et = sti + x2 // 32\n",
    "        if st == et:\n",
    "            l1 = x2 - x1 + 1\n",
    "            e0 = (x2 // 32 + 1) * 32 - x2 - 1\n",
    "            r[st] = int('1' * l1 + '0' * e0, 2)\n",
    "        else:\n",
    "            e1 = (x1 // 32 + 1) * 32 - x1\n",
    "            r[st] = int('1' * e1, 2) if e1 < 32 else -1\n",
    "            for j in range(st + 1, et):\n",
    "                r[j] = -1\n",
    "            s1 = x2 - x2 // 32 * 32\n",
    "            r[et] = -int('0' + '1' * (31 - s1), 2) - 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        ans = [0]*length\n",
    "        start = y*w//32 + (x1 // 32)\n",
    "        end = y*w//32 + (x2 // 32)\n",
    "\n",
    "        #中间肯定都为0xffffffff，所以直接置为-1\n",
    "        for i in range(start+1, end):\n",
    "            ans[i] = -1\n",
    "\n",
    "        #开始和结束端点分别处理\n",
    "        ans[start] = 0xffffffff >> (x1 % 32)\n",
    "        temp_end = (0xffffffff << (31 - (x2  % 32))) & 0xffffffff\n",
    "        ans[end] = temp_end & ans[start] if start == end else temp_end\n",
    "\n",
    "        #求补码\n",
    "        for i in [start, end]:\n",
    "            if ans[i] & 0x80000000 == 0x80000000: \n",
    "                ans[i] = -((ans[i]^0xffffffff)+1)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# 如果最高位为1，表示该数n应该为负数，其真值部分应该是(n^0xffffffff)+1，与1异或等于取反操作。\n",
    "# 作者：cupcdown\n",
    "# 链接：https://leetcode.cn/problems/draw-line-lcci/solutions/693524/pythonshi-yong-yi-huo-qiu-bu-ma-by-cupcd-x0d9/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [0]*length\n",
    "        i, j = x1//32, x2//32\n",
    "        cnt = w//32\n",
    "        sta = (1<<(32-x1%32))-1\n",
    "        end = ((1<<(x2%32+1))-1)<<(31-x2%32)\n",
    "        flag = -1 if (end>>31)&1 else 1\n",
    "        flag1 = -1 if (sta>>31)&1 else 1\n",
    "        end = -(end^(0xffffffff))-1 if flag==-1 else end\n",
    "        sta = -(sta^(0xffffffff))-1 if flag1==-1 else sta\n",
    "        if i==j:res[y*cnt+x1//32]=sta&end\n",
    "        else:\n",
    "            # print(y*cnt+x1//32,(y+1)*cnt,i,j,cnt)\n",
    "            res[y*cnt+x1//32:y*cnt+x2//32+1] = [sta]+[-1]*(j-i-1)+[end]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        ans = [0]*length\n",
    "        start = y*w//32 + (x1 // 32)\n",
    "        end = y*w//32 + (x2 // 32)\n",
    "\n",
    "        #中间肯定都为0xffffffff，所以直接置为-1\n",
    "        for i in range(start+1, end):\n",
    "            ans[i] = -1\n",
    "\n",
    "        #开始和结束端点分别处理\n",
    "        ans[start] = 0xffffffff >> (x1 % 32)\n",
    "        temp_end = (0xffffffff << (31 - (x2  % 32))) & 0xffffffff\n",
    "        ans[end] = temp_end & ans[start] if start == end else temp_end\n",
    "\n",
    "        #求补码\n",
    "        for i in [start, end]:\n",
    "            if ans[i] & 0x80000000 == 0x80000000: \n",
    "                ans[i] = -((ans[i]^0xffffffff)+1)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        MAX_INT = 2**31\n",
    "        result = [0]*length\n",
    "        m = w // 32\n",
    "        i1 = x1 // 32 + y*m\n",
    "        i2 = x2 // 32 + y*m\n",
    "        start = y*w+x1\n",
    "        end = y*w+x2\n",
    "        if(i1 == i2):\n",
    "            if(end - start + 1 == 32):\n",
    "                result[i1] = -1\n",
    "            else:\n",
    "                a = 0\n",
    "                for j in range(end, start-1, -1):\n",
    "                    a += 2**(i1*32+31-j)\n",
    "                \n",
    "                result[i1] = a if a < MAX_INT else a % MAX_INT - MAX_INT\n",
    "        else:\n",
    "            if(start == i1*32):\n",
    "                result[i1] = -1\n",
    "            else:\n",
    "                a1 = 0\n",
    "                p = 0\n",
    "                for j in range(i1*32+31,start-1,-1):\n",
    "                    a1 += 2**p\n",
    "                    p += 1\n",
    "                result[i1] = a1 if a1 < MAX_INT else a % MAX_INT - MAX_INT\n",
    "            if(end == i2*32+31):\n",
    "                result[i2] = -1\n",
    "            else:\n",
    "                a2 = 0\n",
    "                p = 31\n",
    "                for j in range(i2*32,end+1):\n",
    "                    a2 += 2**p\n",
    "                    p -= 1\n",
    "                result[i2] = a2 if a2 < MAX_INT else a2 % MAX_INT - MAX_INT\n",
    "            for i in range(i1+1,i2):\n",
    "                result[i] = -1\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        MAX_INT = 2**31\n",
    "        result = [0]*length\n",
    "        m = w // 32\n",
    "        i1 = x1 // 32 + y*m\n",
    "        i2 = x2 // 32 + y*m\n",
    "        start = y*w+x1\n",
    "        end = y*w+x2\n",
    "        if(i1 == i2):\n",
    "            if(end - start + 1 == 32):\n",
    "                result[i1] = -1\n",
    "            else:\n",
    "                a = 0\n",
    "                for j in range(end, start-1, -1):\n",
    "                    a += 2**(i1*32+31-j)\n",
    "                \n",
    "                result[i1] = a if a < MAX_INT else a % MAX_INT - MAX_INT\n",
    "        else:\n",
    "            if(start == i1*32):\n",
    "                result[i1] = -1\n",
    "            else:\n",
    "                a1 = 0\n",
    "                p = 0\n",
    "                for j in range(i1*32+31,start-1,-1):\n",
    "                    a1 += 2**p\n",
    "                    p += 1\n",
    "                result[i1] = a1 if a1 < MAX_INT else a % MAX_INT - MAX_INT\n",
    "            if(end == i2*32+31):\n",
    "                result[i2] = -1\n",
    "            else:\n",
    "                a2 = 0\n",
    "                p = 31\n",
    "                for j in range(i2*32,end+1):\n",
    "                    a2 += 2**p\n",
    "                    p -= 1\n",
    "                result[i2] = a2 if a2 < MAX_INT else a2 % MAX_INT - MAX_INT\n",
    "            for i in range(i1+1,i2):\n",
    "                result[i] = -1\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        ans = [0]*length\n",
    "        start = y*w//32 + (x1 // 32)\n",
    "        end = y*w//32 + (x2 // 32)\n",
    "\n",
    "        #中间肯定都为0xffffffff，所以直接置为-1\n",
    "        for i in range(start+1, end):\n",
    "            ans[i] = -1\n",
    "\n",
    "        #开始和结束端点分别处理\n",
    "        ans[start] = 0xffffffff >> (x1 % 32)\n",
    "        temp_end = (0xffffffff << (31 - (x2  % 32))) & 0xffffffff\n",
    "        ans[end] = temp_end & ans[start] if start == end else temp_end\n",
    "\n",
    "        #求补码\n",
    "        for i in [start, end]:\n",
    "            if ans[i] & 0x80000000 == 0x80000000: \n",
    "                ans[i] = -((ans[i]^0xffffffff)+1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [0]*length\n",
    "        i, j = x1//32, x2//32\n",
    "        cnt = w//32\n",
    "        sta = (1<<(32-x1%32))-1\n",
    "        end = ((1<<(x2%32+1))-1)<<(31-x2%32)\n",
    "        flag = -1 if (end>>31)&1 else 1\n",
    "        flag1 = -1 if (sta>>31)&1 else 1\n",
    "        end = -(end^(0xffffffff))-1 if flag==-1 else end\n",
    "        sta = -(sta^(0xffffffff))-1 if flag1==-1 else sta\n",
    "        if i==j:res[y*cnt+x1//32]=sta&end\n",
    "        else:\n",
    "            # print(y*cnt+x1//32,(y+1)*cnt,i,j,cnt)\n",
    "            res[y*cnt+x1//32:y*cnt+x2//32+1] = [sta]+[-1]*(j-i-1)+[end]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        neg=0xffffffff\n",
    "        ans=[0]*length\n",
    "        cnt=w//32\n",
    "        line='0'*x1+'1'*(x2-x1+1)+'0'*(w-x2-1)\n",
    "        changed=[]\n",
    "        for i in range(0,w,32):\n",
    "            num=int(line[i:i+32],2)\n",
    "            if line[i]=='1':\n",
    "                num=(num-1)^neg\n",
    "                num=-num\n",
    "            changed.append(num)\n",
    "        ans[y*cnt:(y+1)*cnt]=changed\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        outlist=[]\n",
    "\n",
    "        for i in range(32,w+32,32):\n",
    "            # print(i-1<x1,i-1<=x2,i-32<x1)\n",
    "            if i-1<x1:\n",
    "                outlist.append(0)\n",
    "            elif i-1<=x2:\n",
    "                if i-32<x1:\n",
    "                    outlist.append(int(\"1\"*(i-x1),2))\n",
    "                else:\n",
    "                    outlist.append(-1)\n",
    "            else:\n",
    "                if i-32<=x2:\n",
    "                    if i-32>=x1:\n",
    "                        outlist.append(int(\"1\"*(x2-i+33)+\"0\"*(i-x2-1),2)|(-2147483648))\n",
    "                    else:\n",
    "                        outlist.append(int(\"0\"*(x1-i+32)+\"1\"*(x2-x1+1)+\"0\"*(i-x2-1),2))\n",
    "                else:\n",
    "                    outlist.append(0)\n",
    "\n",
    "        outlist=[0]*(w//32)*y+outlist\n",
    "        outlist.extend([0]*(length-len(outlist)))\n",
    "        outlist=outlist[:length]\n",
    "        return outlist\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        neg = 0xffffffff\n",
    "        ans = [0] * length\n",
    "        cnt = w // 32\n",
    "        line = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - 1 - x2)\n",
    "        #print(line)\n",
    "        changed = []\n",
    "        for i in range(0, w, 32):\n",
    "            num = int(line[i : i + 32], 2)\n",
    "            if line[i] == '1':\n",
    "                num = (num - 1) ^ neg\n",
    "                num = -num \n",
    "            changed.append(num)\n",
    "        ans[y * cnt : (y + 1) * cnt] = changed\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        len_line = x2 - x1 + 1\n",
    "        # 从第几个int开始\n",
    "        startIdx = x1 // 32\n",
    "        # 从第几位开始\n",
    "        SstartPos = x1 % 32\n",
    "        # 到第几个int结束\n",
    "        endIdx = x2 // 32\n",
    "        # 到第几位结束\n",
    "        SendPos = x2 % 32\n",
    "\n",
    "        ret = [0 for _ in range(length)]\n",
    "        st = startIdx + y * (w // 32)\n",
    "        ed = endIdx + y * (w // 32)\n",
    "        #print(\"start:\",st, \"end:\",ed)\n",
    "        for idx in range(st, ed+1):\n",
    "            startPos = 0\n",
    "            endPos = 31\n",
    "            if idx == st:\n",
    "                startPos = SstartPos\n",
    "            if idx == ed:\n",
    "                endPos = SendPos\n",
    "            #print(\"start:\", startPos, \"end:\", endPos)\n",
    "            # 将 startPos到endPos设为1，其余为0\n",
    "            # n 是一个endPos-startPos+1个连续1\n",
    "            # 需要将n左移，使得n的最高位在startPos上\n",
    "            l = (endPos - startPos+1)\n",
    "            n = (2 **l -1)\n",
    "            #左移前n的最高位在第l-1位, 左移后n的最高位在第31-startPos位\n",
    "            # 共需左移 31 - startPos - l位\n",
    "            beforeLeftShift = l - 1\n",
    "            afterLeftShift = 31 - startPos\n",
    "            #print(beforeLeftShift, afterLeftShift, afterLeftShift - beforeLeftShift)\n",
    "\n",
    "            n = n << (afterLeftShift - beforeLeftShift)\n",
    "            # 如果符号位变为1，则会从32位扩展到64位，此时需要把扩展的位全设为1表示负数\n",
    "            if afterLeftShift >= 31:\n",
    "                n |= (-1 << 32)\n",
    "            if startPos == 0 and endPos == 31:\n",
    "                n = -1\n",
    "            #print(\"n\",n)\n",
    "            ret[idx] |= n\n",
    "            ret[idx] &= n\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        MAX_INT = 2**31\n",
    "        result = [0]*length\n",
    "        m = w // 32\n",
    "        i1 = x1 // 32 + y*m\n",
    "        i2 = x2 // 32 + y*m\n",
    "        start = y*w+x1\n",
    "        end = y*w+x2\n",
    "        if(i1 == i2):\n",
    "            if(end - start + 1 == 32):\n",
    "                result[i1] = -1\n",
    "            else:\n",
    "                a = 0\n",
    "                for j in range(end, start-1, -1):\n",
    "                    a += 2**(i1*32+31-j)\n",
    "                \n",
    "                result[i1] = a if a < MAX_INT else a % MAX_INT - MAX_INT\n",
    "        else:\n",
    "            if(start == i1*32):\n",
    "                result[i1] = -1\n",
    "            else:\n",
    "                a1 = 0\n",
    "                p = 0\n",
    "                for j in range(i1*32+31,start-1,-1):\n",
    "                    a1 += 2**p\n",
    "                    p += 1\n",
    "                result[i1] = a1 if a1 < MAX_INT else a % MAX_INT - MAX_INT\n",
    "            if(end == i2*32+31):\n",
    "                result[i2] = -1\n",
    "            else:\n",
    "                a2 = 0\n",
    "                p = 31\n",
    "                for j in range(i2*32,end+1):\n",
    "                    a2 += 2**p\n",
    "                    p -= 1\n",
    "                result[i2] = a2 if a2 < MAX_INT else a2 % MAX_INT - MAX_INT\n",
    "            for i in range(i1+1,i2):\n",
    "                result[i] = -1\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        n = w // 32\n",
    "        ans = [0] * length\n",
    "        a = (x1 // 32) + y * n\n",
    "        b = (x2 // 32) + y * n\n",
    "        p = x1 % 32\n",
    "        q = x2 % 32\n",
    "        if a == b:\n",
    "            t = ans[a]\n",
    "            if p == 0:\n",
    "                ans[a] = -(1 << (31- q))\n",
    "            else:\n",
    "                ans[a] = (1 << (32 - p)) - (1 << (31 - q))\n",
    "        else:\n",
    "            t = ans[a]\n",
    "            if p == 0:\n",
    "                ans[a] = -1\n",
    "            else:\n",
    "                t = (1 << (32 - p)) - 1\n",
    "                ans[a] = t\n",
    "            # print(ans)\n",
    "            t = ans[b]\n",
    "            ans[b] = -(1 << (31- q))\n",
    "            for i in range(a+1, b):\n",
    "                ans[i] = -1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        neg=0xffffffff\n",
    "        ans=[0]*length\n",
    "        cnt=w//32\n",
    "        line='0'*x1+'1'*(x2-x1+1)+'0'*(w-x2-1)\n",
    "        changed=[]\n",
    "        for i in range(0,w,32):\n",
    "            num=int(line[i:i+32],2)\n",
    "            if line[i]=='1':\n",
    "                num=(num-1)^neg\n",
    "                num=-num\n",
    "            changed.append(num)\n",
    "        ans[y*cnt:(y+1)*cnt]=changed\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        neg=0xffffffff\n",
    "        cnt=w//32\n",
    "        ans=[0]*length\n",
    "        line='0'*x1+'1'*(x2-x1+1)+ '0'*(w-x2+1)\n",
    "        changed=[]\n",
    "        for i in range (0,w,32):\n",
    "            num=int(line[i:i+32],2)\n",
    "            if line[i]=='1':\n",
    "                num=(num-1)^neg\n",
    "                num=-num\n",
    "            changed.append(num)\n",
    "        ans[y*cnt:(y+1)*cnt]=changed\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        scene = [0] * length\n",
    "        i = y * w // 32 + x1 // 32\n",
    "        for j in range(x1, x2 + 1):\n",
    "            scene[i] |= 1 << (31 - j % 32)\n",
    "            if j % 32 == 31:\n",
    "                i += 1\n",
    "        return [pixs - (1 << 32) if pixs & (1 << 31) else pixs for pixs in scene]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        neg = 0xffffffff\n",
    "        ans = [0] * length\n",
    "        cnt = w // 32\n",
    "        line = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - 1 - x2)\n",
    "        #print(line)\n",
    "        changed = []\n",
    "        for i in range(0, w, 32):\n",
    "            num = int(line[i : i + 32], 2)\n",
    "            if line[i] == '1':\n",
    "                num = (num - 1) ^ neg\n",
    "                num = -num \n",
    "            changed.append(num)\n",
    "        ans[y * cnt : (y + 1) * cnt] = changed\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [0]*(length)\n",
    "        for i in range(x1, x2+1):\n",
    "            width = w // 32\n",
    "            res[width * y + (i // 32)] |= (1 << (31 - (i % 32)))\n",
    "        \n",
    "        for i in range(len(res)):\n",
    "            if res[i] & (2 ** 31):\n",
    "                res[i] ^= (2**32 - 1)\n",
    "                res[i] = -res[i] - 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        neg = 0xffffffff\n",
    "        ans = [0] * length\n",
    "        cnt = w // 32\n",
    "        line = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - 1 - x2)\n",
    "        #print(line)\n",
    "        changed = []\n",
    "        for i in range(0, w, 32):\n",
    "            num = int(line[i : i + 32], 2)\n",
    "            if line[i] == '1':\n",
    "                num = (num - 1) ^ neg\n",
    "                num = -num \n",
    "            changed.append(num)\n",
    "        ans[y * cnt : (y + 1) * cnt] = changed\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        INT_MAX = (1<<31) - 1\n",
    "        ans = [0] * length\n",
    "        \n",
    "        b = (y*w) // 32\n",
    "        for i in range(x1, x2+1):\n",
    "            idx = i // 32\n",
    "            mask = 1 << (31-i%32)\n",
    "            ans[idx+b] |= mask\n",
    "        \n",
    "        toInt32 = lambda x: x if x <= INT_MAX else -((~x+1)&INT_MAX)\n",
    "        ans = [toInt32(i) for i in ans]\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        ans = [0 for i in range(length)]\n",
    "        start = y * (w // 32) + (x1 // 32)\n",
    "        nowsite = 31 - (x1 % 32)\n",
    "        count = x2 - x1 + 1\n",
    "\n",
    "        while count:\n",
    "            ans[start] |= (1 << nowsite)\n",
    "            nowsite -= 1\n",
    "            if nowsite == -1:\n",
    "                start += 1\n",
    "                nowsite = 31\n",
    "\n",
    "            count -= 1\n",
    "        for i in range(len(ans)):\n",
    "            ans[i] &= ((1<<32)-1)\n",
    "            if ans[i] & (1<<31): ans[i] -= (1<<32)\n",
    "            # return val\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "\n",
    "        neg = 0xffffffff\n",
    "\n",
    "        ans = [0] * length\n",
    "\n",
    "        cnt = w // 32\n",
    "\n",
    "        line = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - 1 - x2)\n",
    "\n",
    "        #print(line)\n",
    "\n",
    "        changed = []\n",
    "\n",
    "        for i in range(0, w, 32):\n",
    "\n",
    "            num = int(line[i : i + 32], 2)\n",
    "\n",
    "            if line[i] == '1':\n",
    "\n",
    "                num = (num - 1) ^ neg\n",
    "\n",
    "                num = -num \n",
    "\n",
    "            changed.append(num)\n",
    "\n",
    "        ans[y * cnt : (y + 1) * cnt] = changed\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        neg = 0xffffffff\n",
    "        ans = [0] * length\n",
    "        cnt = w // 32\n",
    "        line = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - 1 - x2)\n",
    "        changed = []\n",
    "        for i in range(0, w, 32):\n",
    "            num = int(line[i : i + 32], 2)\n",
    "            if line[i] == '1':\n",
    "                num = (num - 1) ^ neg\n",
    "                num = -num \n",
    "            changed.append(num)\n",
    "        ans[y * cnt : (y + 1) * cnt] = changed\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        len_line = x2 - x1 + 1\n",
    "        # 从第几个int开始\n",
    "        startIdx = x1 // 32\n",
    "        # 从第几位开始\n",
    "        SstartPos = x1 % 32\n",
    "        # 到第几个int结束\n",
    "        endIdx = x2 // 32\n",
    "        # 到第几位结束\n",
    "        SendPos = x2 % 32\n",
    "\n",
    "        ret = [0 for _ in range(length)]\n",
    "        st = startIdx + y * (w // 32)\n",
    "        ed = endIdx + y * (w // 32)\n",
    "        print(\"start:\",st, \"end:\",ed)\n",
    "        for idx in range(st, ed+1):\n",
    "            startPos = 0\n",
    "            endPos = 31\n",
    "            if idx == st:\n",
    "                startPos = SstartPos\n",
    "            if idx == ed:\n",
    "                endPos = SendPos\n",
    "            print(\"start:\", startPos, \"end:\", endPos)\n",
    "            # 将 startPos到endPos设为1，其余为0\n",
    "            # n 是一个endPos-startPos+1个连续1\n",
    "            # 需要将n左移，使得n的最高位在startPos上\n",
    "            l = (endPos - startPos+1)\n",
    "            n = (2 **l -1)\n",
    "            #左移前n的最高位在第l-1位, 左移后n的最高位在第31-startPos位\n",
    "            # 共需左移 31 - startPos - l位\n",
    "            beforeLeftShift = l - 1\n",
    "            afterLeftShift = 31 - startPos\n",
    "            print(beforeLeftShift, afterLeftShift, afterLeftShift - beforeLeftShift)\n",
    "\n",
    "            n = n << (afterLeftShift - beforeLeftShift)\n",
    "            # 如果符号位变为1，则会从32位扩展到64位，此时需要把扩展的位全设为1表示负数\n",
    "            if afterLeftShift >= 31:\n",
    "                n |= (-1 << 32)\n",
    "            if startPos == 0 and endPos == 31:\n",
    "                n = -1\n",
    "            print(\"n\",n)\n",
    "            ret[idx] |= n\n",
    "            ret[idx] &= n\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        neg = 0xffffffff\n",
    "        ans = [0] * length\n",
    "        cnt = w // 32\n",
    "        line = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - 1 - x2)\n",
    "        #print(line)\n",
    "        changed = []\n",
    "        for i in range(0, w, 32):\n",
    "            num = int(line[i : i + 32], 2)\n",
    "            if line[i] == '1':\n",
    "                num = (num - 1) ^ neg\n",
    "                num = -num \n",
    "            changed.append(num)\n",
    "        ans[y * cnt : (y + 1) * cnt] = changed\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        r = w // 32\n",
    "        h = length // r\n",
    "        ans = []\n",
    "        ans += [0] * y * r\n",
    "        p1 = 0\n",
    "        p2 = 31\n",
    "        while p2 < x1:\n",
    "            p1 = p2 + 1\n",
    "            p2 += 32\n",
    "            ans.append(0)\n",
    "        while p1 <= x2:\n",
    "            if p1 < x1:\n",
    "                ans.append(2**(p2 - x1+1) - 2**(max(0, p2 - x2)))\n",
    "            else:\n",
    "                ans.append(-(2**(max(p2 - x2, 0))))\n",
    "            p1 = p2 + 1\n",
    "            p2 += 32\n",
    "        ans.extend([0] * ((w - p1)//32 + (h-1-y)*r))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        neg = 0xffffffff\n",
    "        ans = [0] * length\n",
    "        cnt = w // 32\n",
    "        line = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - 1 - x2)\n",
    "        #print(line)\n",
    "        changed = []\n",
    "        for i in range(0, w, 32):\n",
    "            num = int(line[i : i + 32], 2)\n",
    "            if line[i] == '1':\n",
    "                num = (num - 1) ^ neg\n",
    "                num = -num \n",
    "            changed.append(num)\n",
    "        ans[y * cnt : (y + 1) * cnt] = changed\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        if x1 > x2:\n",
    "            x1, x2 = x2, x1\n",
    "        s = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - x2 - 1)\n",
    "        ans = []\n",
    "        ans += [0] * (w // 32) * y\n",
    "        for i in range(0, len(s), 32):\n",
    "            if s[i] == '1':\n",
    "                p = -((int(s[i:i + 32], 2) ^ (2 ** 32 - 1)) + 1)\n",
    "                ans.append(p)\n",
    "            else:\n",
    "                ans.append(int(s[i:i + 32], 2))\n",
    "                \n",
    "        h = length * 32 // w\n",
    "        ans += [0] * (w // 32) * (h - y - 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        # 定义32位的负数掩码\n",
    "        neg_mask = 0xffffffff\n",
    "        ans = [0] * length\n",
    "        cnt = w // 32\n",
    "        # 生成该行的像素表示\n",
    "        line = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - 1 - x2)\n",
    "        \n",
    "        changed = []\n",
    "        for i in range(0, w, 32):\n",
    "            num = int(line[i : i + 32], 2)\n",
    "            if line[i] == '1':\n",
    "                # 如果这32位的开始是1，使用补码表示负数\n",
    "                num = (num - 1) ^ neg_mask\n",
    "                num = -num \n",
    "            changed.append(num)\n",
    "        \n",
    "        # 将修改后的数字放到结果数组的对应位置\n",
    "        ans[y * cnt : (y + 1) * cnt] = changed\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        if x1 > x2:\n",
    "            x1, x2 = x2, x1\n",
    "        s = '0' * x1 + '1' * (x2 - x1 + 1) + '0' * (w - x2 - 1)\n",
    "        ans = []\n",
    "        for i in range(y):\n",
    "            ans += [0 for _ in range(w // 32)]\n",
    "        for i in range(0, len(s), 32):\n",
    "            if s[i] == '1':\n",
    "                p = -((int(s[i:i + 32], 2) ^ (2 ** 32 - 1)) + 1)\n",
    "                ans.append(p)\n",
    "            else:\n",
    "                ans.append(int(s[i:i + 32], 2))\n",
    "                \n",
    "        h = length * 32 // w\n",
    "        for i in range(h - y - 1):\n",
    "            ans += [0 for _ in range(w // 32)]\n",
    "        \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> list[int]:\n",
    "        result=[]\n",
    "        word1='0'*x1\n",
    "        word2='1'*(x2-x1+1)\n",
    "        word3='0'*(w-x2-1)\n",
    "        word=word1+word2+word3\n",
    "        n=int(w/32)\n",
    "        for i in range(int(n)):\n",
    "            num=word[i*32:(i+1)*32]\n",
    "            if num[0]=='0':\n",
    "                result.append(int(num,2))\n",
    "            else:\n",
    "                binary_out = list(num)\n",
    "                for epoch, i in enumerate(binary_out):\n",
    "                    #enumerate()函数用于一个可遍历的数据对象，同时获得下标和数据内的内容\n",
    "                    if i == \"0\":\n",
    "                        binary_out[epoch] = \"1\"\n",
    "                    else:\n",
    "                        binary_out[epoch] = \"0\"\n",
    "                num=''.join(binary_out)\n",
    "                result.append(-(int(num,2)+1))\n",
    "        result0=[0]*y*(n)\n",
    "        result1=[0]*(int(length*32/w)-y-1)*n\n",
    "        return result0+result+result1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        words = w // 32\n",
    "\n",
    "        res = list(0 for _ in range(words * y))\n",
    "        \n",
    "        s = '0' * x1 + '1' * (x2-x1+1) + '0' * (w-x2-1)\n",
    "\n",
    "        for i in range(words):\n",
    "            toadd = int(s[i*32 : (i+1)*32], 2)\n",
    "            if toadd & (1<<31):\n",
    "                toadd |= ~((1<<32) - 1)\n",
    "            res.append(toadd)\n",
    "        \n",
    "        if length <= len(res):\n",
    "            return res[:length]\n",
    "        l = len(res)\n",
    "        res.extend(list(0 for _ in range(length - l)))\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        out = [0 for i in range(length)]\n",
    "        width = w // 32\n",
    "        start = y * width + x1 // 32\n",
    "        b_nums = []     # 发生变化的二进制数组\n",
    "        for i in range(x1//32*32, x2//32*32+32):\n",
    "            if x1 <= i <= x2: b_nums.append(1)\n",
    "            else: b_nums.append(0)\n",
    "        # 一共几个元素发生了改变\n",
    "        count = len(b_nums) // 32\n",
    "        for i in range(count):\n",
    "            a = b_nums[i*32 : i*32+32]\n",
    "            positive_flag = True\n",
    "            # 判断是否为负数\n",
    "            if a[0] == 1:\n",
    "                positive_flag = False\n",
    "                # 减1操作\n",
    "                for j in range(31, -1, -1):\n",
    "                    if a[j] == 0:\n",
    "                        a[j] = 1\n",
    "                    else:\n",
    "                        a[j] = 0\n",
    "                        break\n",
    "                #按位取反操作\n",
    "                for j in range(32):\n",
    "                    if a[j] == 0:\n",
    "                        a[j] = 1\n",
    "                    else:\n",
    "                        a[j] = 0\n",
    "            ten = 0\n",
    "            for k in range(32):\n",
    "                ten = ten + a[k] * pow(2, 31-k)\n",
    "            if not positive_flag:\n",
    "                ten = ten * (-1)    # 负数需要乘以-1\n",
    "            out[start] = ten\n",
    "            start += 1\n",
    "        return list(map(int, out))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        def change(list1):\n",
    "            ans = 0\n",
    "            for i in range(len(list1)-1, -1, -1):\n",
    "                ans += (2**(len(list1) - 1 - i)) * list1[i]\n",
    "            if list1[0] == 1:\n",
    "                temp = ans - 1\n",
    "                temp = temp ^ 0xffffffff\n",
    "                ans = -temp\n",
    "            return ans\n",
    "        ans1 = [0] * length\n",
    "        idx = 0\n",
    "        for i in range(y):\n",
    "            for j in range(w//32):\n",
    "                idx += 1\n",
    "\n",
    "        temp = [0] * w\n",
    "        for i in range(len(temp)):\n",
    "            if (i>=x1) and (i<=x2):\n",
    "                temp[i] = 1\n",
    "        for i in range(w//32):\n",
    "           ans1[idx] = change(temp[i*32:(i+1)*32])\n",
    "           idx += 1\n",
    "\n",
    "        return ans1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# copied\n",
    "\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        maxtrix = [['0'] * 32 for _ in range(length)]\n",
    "        res = []\n",
    "        start, end = x1 + y * w, x2 + y * w\n",
    "        one_31 = (1 << 31) - 1\n",
    "        for idx in range(start, end + 1):\n",
    "            i, j = divmod(idx, 32)\n",
    "            maxtrix[i][j] = '1'\n",
    "        for row in maxtrix:\n",
    "            sign, val = row[0], int(''.join(row[1:]), 2)\n",
    "            if sign == '0':\n",
    "                res.append(val)\n",
    "            else:\n",
    "                val = (val ^ one_31) + 1\n",
    "                res.append(-val)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [0]*length\n",
    "        i, j = x1//32, x2//32\n",
    "        cnt = w//32\n",
    "        sta = (1<<(32-x1%32))-1\n",
    "        end = ((1<<(x2%32+1))-1)<<(31-x2%32)\n",
    "        flag = -1 if (end>>31)&1 else 1\n",
    "        flag1 = -1 if (sta>>31)&1 else 1\n",
    "        end = -(end^(0xffffffff))-1 if flag==-1 else end\n",
    "        sta = -(sta^(0xffffffff))-1 if flag1==-1 else sta\n",
    "        if i==j:res[y*cnt+x1//32]=sta&end\n",
    "        else:\n",
    "            # print(y*cnt+x1//32,(y+1)*cnt,i,j,cnt)\n",
    "            res[y*cnt+x1//32:y*cnt+x2//32+1] = [sta]+[-1]*(j-i-1)+[end]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [[0]*(w//32) for _ in range(length//(w//32))]\n",
    "        i, j = x1//32, x2//32\n",
    "        sta = (1<<(32-x1%32))-1\n",
    "        end = ((1<<(x2%32+1))-1)<<(31-x2%32)\n",
    "        flag = -1 if (end>>31)&1 else 1\n",
    "        flag1 = -1 if (sta>>31)&1 else 1\n",
    "        end = -(end^((1<<32)-1))-1 if flag==-1 else end\n",
    "        sta = -(sta^((1<<32)-1))-1 if flag1==-1 else sta\n",
    "        if i==j:res[y][i]=sta&end\n",
    "        else:\n",
    "            res[y][i:j+1] = [sta]+[-1]*(j-i-1)+[end]\n",
    "        ans = []\n",
    "        for c in res:\n",
    "            ans += c\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [[0]*(w//32) for _ in range(length//(w//32))]\n",
    "        i, j = x1//32, x2//32\n",
    "        sta = (1<<(32-x1%32))-1\n",
    "        end = ((1<<(x2%32+1))-1)<<(31-x2%32)\n",
    "        flag = -1 if (end>>31)&1 else 1\n",
    "        flag1 = -1 if (sta>>31)&1 else 1\n",
    "        end = -(end^(0xffffffff))-1 if flag==-1 else end\n",
    "        sta = -(sta^(0xffffffff))-1 if flag1==-1 else sta\n",
    "        if i==j:res[y][i]=sta&end\n",
    "        else:\n",
    "            res[y][i:j+1] = [sta]+[-1]*(j-i-1)+[end]\n",
    "        ans = []\n",
    "        for c in res:\n",
    "            ans += c\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def drawLine(self, length: int, w: int, x1: int, x2: int, y: int) -> List[int]:\n",
    "        res = [0]*length\n",
    "        i, j = x1//32, x2//32\n",
    "        cnt = w//32\n",
    "        sta = (1<<(32-x1%32))-1\n",
    "        end = ((1<<(x2%32+1))-1)<<(31-x2%32)\n",
    "        flag = -1 if (end>>31)&1 else 1\n",
    "        flag1 = -1 if (sta>>31)&1 else 1\n",
    "        end = -(end^(0xffffffff))-1 if flag==-1 else end\n",
    "        sta = -(sta^(0xffffffff))-1 if flag1==-1 else sta\n",
    "        if i==j:res[y*cnt+x1//32]=sta&end\n",
    "        else:\n",
    "            # print(y*cnt+x1//32,(y+1)*cnt,i,j,cnt)\n",
    "            res[y*cnt+x1//32:y*cnt+x2//32+1] = [sta]+[-1]*(j-i-1)+[end]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
